class Solution {
    bool check(int x, int y)
    {
        if(y <= 0.5 * x + 7 || y > x || (y > 100 && x < 100))
            return false;
        return true;
    }
public:
    int numFriendRequests(vector<int>& ages) {
        // 滑动窗口，时间复杂度为O(N*logN)
        // 满足下面这三个条件则不发送
        // ages[y] <= 0.5 * ages[x] + 7
        // ages[y] > ages[x]
        // ages[y] > 100 && ages[x] < 100
        // 那反过来就是
        // ages[y] > 0.5 * ages[x] + 7
        // ages[y] <= ages[x]
        // ages[y] <= 100 || ages[x] >= 100，这个条件是冗余的，可以去掉
        // 也就是剩下面两种条件
        // ages[y] > 0.5 * ages[x] + 7
        // ages[y] <= ages[x]
        // 所以合并为
        // 0.5 * ages[x] + 7 < ages[y] <= ages[x]
        // 由此可得 0.5 * ages[x] + 7 < ages[x]   --->    ages[x] > 14
        // 说明ages[y] ∈ (0.5 * ages[x] + 7, ages[x]]，所以要维护这个窗口
        // 因为题目中明确说明用户不会向自己发送好友请求，所以要去掉右端点，每次更新窗口要减 1
        int n = ages.size(), ret = 0;
        sort(ages.begin(), ages.end());
        for(int i = 0, left = 0, right = 0; i < n; i++)
        {
            if(ages[i] <= 14)
                continue;
            while(ages[left] <= 0.5 * ages[i] + 7)
                left++;
            while(right < n && ages[right] <= ages[i])
                right++;
            ret += right - left - 1;
        }
        return ret;

        // 暴力做法，O(N^2)，超时
        // int n = ages.size(), ret = 0;
        // for(int i = 0; i < n; i++)
        // {
        //     for(int j = 0; j < n; j++)
        //     {
        //         if(i == j)
        //             continue;
                
        //         int x = ages[i], y = ages[j];
        //         if(check(x, y))
        //             ret++;
        //     }
        // }
        // return ret;
    }
};